package com.fzy.leetcode.editor.cn;
//2023-03-25 11:53:28
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
//
// Related Topics 字符串 动态规划 👍 6312 👎 0

import java.util.Arrays;

class LongestPalindromicSubstring {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new LongestPalindromicSubstring().new Solution();
        solution.longestPalindrome("babad");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();

        int[][] dp = new int[n+1][n+1];
        char[] str = s.toCharArray();
        StringBuilder stringBuilder = new StringBuilder(s);
        stringBuilder.reverse();
        char[] str2 = stringBuilder.toString().toCharArray();
        int ans = 0;
        for(int i = 1;i<n;i++){
            for(int j = 1;j<n;j++){
                if(str[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(ans<dp[i][j]){
                    ans = dp[i][j];
                }
            }
        }

        return String.valueOf(ans);
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}